درسنامه آموزشی فصل دوم ریاضیات گسسته کلاس دوازدهم ریاضی

در اوایل قرن هجدهم، معمایی فکر برخی از اهالی شهر کونیگسبرگ (در حال حاضر در روسیه) را به خود مشغول کرده بود.

رودخانهٔ این شهر که از میان شهر عبور می‌کرد مانند آنچه در شکل زیر می‌بینید، شهر را به چند قسمت تقسیم می‌کرد. برخی از مردم این شهر کنجکاو بودند که بدانند آیا می‌توان با حرکت از یک نقطه از شهر و دقیقاً یکبار عبور از هر کدام از پل‌ها، به نقطهٔ شروع حرکت بازگشت؟

لئونارد اویلر (1783-1707)، ریاضی‌دان برجستهٔ سوئیسی، برای حل این مسئله از شکل زیر، که امروزه به آن «گراف» می‌گوییم، کمک گرفت و با استفاده از استدلال ثابت کرد که این کار امکان‌پذیر نیست.

اگر چهار ناحیهٔ x و y و z و w را با 4 نقطه نمایش دهیم و به‌ازای هر پل که بین دو ناحیه قرار دارد نقاط متناظر با آن ناحیه‌ها را به هم وصل نماییم شکل زیر به‌دست می‌آید که گرافِ حاصل از مدل‌سازی مسئلهٔ مذکور است.

مدل‌سازی بسیاری از مسائل با گراف، دسته‌بندی منظم و تفکر منطقی درباره آنها را آسان‌تر می‌نماید.

اگرچه بیش‌تر مورخان تاریخ ریاضی شروع بحث گراف را از این مسئلهٔ اویلر می‌دانند، اما بی‌تردید متفکران و ریاضی‌دانان دیگری پیش از آن تاریخ نیز برای حل مسائل از مدل‌سازی با گراف بهره گرفته‌اند. به‌طور مثال در حدود 100 سال پیش از آن شیخ بهایی، ریاضی‌دان ایرانی (1000-925 خورشیدی) مسئله‌ای به این‌صورت طرح کرد:

سه خانه و سه چاه آب، مانند شکل مقابل مفروض‌اند. آیا می‌توان از هر چاه به هر خانه یک کانال آب حفر کرد به‌طوری‌که هیچ دو کانالی یکدیگر را قطع نکنند؟

حل این مسئله هم ارتباط نزدیکی به مباحث گراف دارد. اگر خانه‌ها و چاه‌ها را 6 نقطه مشخص کنیم و کانال‌ها را با خط‌ها یا منحنی‌ها نمایش دهیم در این‌صورت دو مجموعهٔ مجزای 3 عضوی از نقاط داریم که باید نقاط مجموعهٔ اوّل به تک‌تک نقاط مجموعهٔ دوم وصل شوند. شکل حاصل از این کار یک گراف است و می‌توان نشان داد که این کار نشدنی است و لااقل دو تا از خط‌ها یکدیگر را قطع می‌کنند.

حال به مثالی از تحلیل یک وضعیت به‌کمک گراف می‌پردازیم.

مثال: 5 تیم فوتبال d ،c ،b ، a و e در یک گروه قرار دارند و تیم‌ها ‌دو به دو با هم بازی ‌کنند و برخی از این بازی‌ها انجام شده است و اطلاعات زیر را داریم:

تیم a تیم‌های b و e را برده و به c باخته است.
تیم b به a باخته و از d برده است.
تیم c از تیم‌های a و e برده است.
تیم d یه تیم‌های b و e باخته است.
تیم e به a و c باخته و از تیم d برده است.

برای نمایش تمام اطلاعات بالا به‌صورت خلاصه، از نموداری به شکل 4 استفاده می‌کنیم که به‌ازای هر تیم یک نقطه می‌گذاریم و هر دو نقطه را به هم وصل می‌کنیم اگر و تنها اگر تیم‌های مربوط به آنها با هم بازی کرده باشند؛ و جهت خط یا منحنی‌ای که دو نقطه را به هم وصل می‌کند باید از تیم برنده به‌سمت تیم بازنده باشد.

حال با یک نگاه به نمودار رسم شده، علاوه بر دریافت اطلاعات بالا به‌سادگی به سؤال‌های زیر نیز می‌توان جواب داد.
- مشخص کنید هر تیم با کدام تیم‌ها بازی نکرده است.
- اگر هر برد 3 امتیاز داشته باشد در بازی‌هایی که تا اینجا انجام شده است کدام تیم‌ها بیشترین امتیاز را کسب کرده‌اند؟

مسئله: سؤال دیگری مطرح کنید که با دیدن نمودار گرافِ مثال قبل بتوان به آن جواب داد.

همان‌طور که دیدیم یک گراف متشکل است از مجموعه‌ای از نقاط و مجموعه‌ای از پاره‌خط‌ها، که به هر یک از این نقاط رأس و به هر یک از پاره‌خط‌ها یال می‌گوییم. توجه کنید که یال‌ها لازم نیست حتماً پاره‌خط راست باشند و می‌توانند به‌صورت منحنی نیز باشند و در هر سِر یال باید رأسی قرار داشته باشد. همان‌طور که دیدیم یک گراف را می‌توان با رسم نمودارِ آن نشان داد و نیز می‌توان آن‌را با نمادهای ریاضی معرفی کرد. در ادامه به شکلی ساده چند تعریف مقدماتی و نحوهٔ نمایش یک گراف را بررسی می‌کنیم.

گراف G را با 9 رأس و 10 یال، مانند شکل 5، در نظر می‌گیریم و با بررسی آن برخی تعاریف را نیز مطرح می‌نماییم.

با توجه به اینکه یک گراف مجموعه‌ای از رئوس و یال‌هاست می‌توان به‌جای نمایش آن با شکل بالا، با نمادهای ریاضی مجموعهٔ یال‌ها و رئوس آن‌را به‌صورت زیر نمایش داد.

$V(G)=\left\{ {{v}_{1}},{{v}_{2}},...,{{v}_{8}},{{v}_{9}} \right\}$ :مجموعه رأس‌های گراف G 
$E(G)=\left\{ {{v}_{1}}{{v}_{2}},{{v}_{1}}{{v}_{4}},{{v}_{1}}{{v}_{8}},{{v}_{2}}{{v}_{3}},{{v}_{2}}{{v}_{5}},{{v}_{4}}{{v}_{5}},{{v}_{4}}{{v}_{6}},{{v}_{5}}{{v}_{7}},{{v}_{6}}{{v}_{8}},{{v}_{7}}{{v}_{8}} \right\}$ :مجموعه یال‌های گراف G 

به وضوح، با داشتن شکلِ گراف، شما می‌توانید مجموعه‌های $V(G)$ و $E(G)$ را بنویسید و همچنین با داشتن دو مجموعهٔ $V(G)$ و $E(G)$ می‌توانید ابتدا به تعداد $n(V(G))$ (تعداد اعضای مجموعهٔ $V(G)$ که آن‌را با $\left| V(G) \right|$ نیز نمایش می‌دهیم) نقطه (رأس) مشخص نمایید و سپس با توجه به $E(G)$ رأس‌های متناظر را به هم وصل نمایید.

همان‌طور که در مثال تیم‌های فوتبال ملاحظه کردید گاهی اوقات لازم است برای یال‌ها جهت تعیین کنیم.

به گرافی که برای یال‌های آن جهت تعیین شده باشد، گراف جهت‌دار می‌گوییم. در این حالت برای نمایش اینکه جهت یک یال از سمت کدام رأس به‌سمت کدام رأس است یال‌ها را با زوج مرتب نمایش می‌دهیم. به‌طور مثال مجموعهٔ رئوس و یال‌های گراف جهت‌دار شکل 6 را این‌گونه نمایش می‌دهیم.

$V=\left\{ a,b,c,d \right\}$
$E=\left\{ (a,b),(a,c),(c,a),(d,b) \right\}$

توجه: برای رسم نمودار یک گراف (شکل گراف) روش یکتایی مدنظر نیست. آنچه مهم است این است که باید مشخص باشد که گراف مورد نظر چند رأس و چند یال دارد و کدام یال به کدام رئوس متصل است. به‌طور مثال با نوشتن مجموعه‌های $V(G)$ و $E(G)$ برای هر یک از شکل‌های زیر، نشان دهید هر دو یک گراف را نمایش می‌دهند.

$V({{G}_{1}})=\left\{ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \right\}$
$E({{G}_{1}})=\left\{ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \right\}$

$V({{G}_{2}})=\left\{ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \right\}$
$E({{G}_{2}})=\left\{ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \right\}$

- مرتبه و اندازهٔ یک گراف: تعداد رأس‌های گراف G یعنی $\left| V(G) \right|$ را مرتبهٔ آن گراف می‌گوییم و با $p(G)$ نمایش می‌دهیم و تعداد یال‌های گراف یعنی $\left| E(G) \right|$ را اندازهٔ گراف G می‌گوییم و با $q(G)$ نمایش می‌دهیم. 

معمولاً برای راحتی کار به‌جای $p(G)$ از $p$ و به‌جای $q(G)$ از $q$ استفاده می‌کنیم. به‌طور مثال گراف‌های نمایش داده شده در شکل 7 از مرتبهٔ 5 و اندازهٔ 6 هستند. بنابراین $p=5$ و $q=6$.

- درجهٔ یک رأس: درجهٔ رأس v در گراف G برابر است با تعداد یال‌هایی از گراف G که به رأس v متصل‌اند و آن‌را با ${{\deg }_{G}}(v)$ یا به‌طور ساده‌تر با ${{\deg }_{G}}(v)$ یا $d(v)$ نمایش می‌دهیم. اگر درجهٔ یک رأس فرد باشد آن‌را رأس فرد و اگر زوج باشد آن‌را رأس زوج می‌نامیم. به‌طور مثال در شکل زیر داریم:

$\deg ({{v}_{1}})=3$
$\deg ({{v}_{5}})=4$

- گراف $-k$ منتظم: گرافی را که درجهٔ تمام رئوس آن با هم مساوی و برابر با عدد $k$ باشند، گراف $-k$ منتظم می‌نامیم. مثلاً گراف شکل 9 یک گراف 6 رأسی $-3$ منتظم است.

- رأس تنها: به رأسی که درجهٔ آن صفر باشد؛ یعنی هیچ یالی به آن متصل نباشد، رأس تنها (یا ایزوله) می‌گوییم.

- گرافی را که تنها رئوس آن رأس تنها باشند، یعنی هیچ یالی نداشته باشد، گراف تهی می‌نامیم. بنابراین منظور از گراف تهی n رأسی، گرافی شامل n رأس تنها و بدون یال است.

بین دو رأس از یک گراف ممکن است بیش از یک یال وجود داشته باشد. همچنین یک یال ممکن است یک رأس را به خوِد آن رأس وصل نماید که در این‌صورت به این یال طوقه گفته می‌شود. این دو مورد در شکل 10 نمایش داده شده‌اند. گرافی را که در آن هیچ‌یک از این دو مورد اتفاق نیفتاده باشد را گراف ساده می‌گوییم.

دیدیم که گراف حاصل از مدل‌سازی پل کونیگسبرگ یک گراف ساده نیست. ما در این کتاب فقط گراف‌های ساده را بررسی خواهیم کرد و از این به بعد منظورمان از گراف، گراف ساده است.

- دو رأس مجاور (همسایه): دو رأس u و v را دو رأس همسایه یا مجاور گوییم هرگاه توسط یالی به هم وصل شده باشند، یعنی $uv\in E(G)$. به‌طور مثال در گراف شکل 11، رأس ${{v}_{1}}$ با رئوس ${{v}_{2}}$ و ${{v}_{5}}$ همسایه است و رأس ${{v}_{2}}$ با رئوس ${{v}_{1}}$ و ${{v}_{3}}$ و ${{v}_{4}}$ همسایه است.

توجه: در زمان رسم نمودار یک گراف توجه داشته باشید که هیچ یالی خودش را قطع نکند و همچنین هیچ یالی نباید از روی رأسی که مربوط به دو سر آن یال نیست عبور نماید.

- مجموعهٔ همسایه‌های یک رأس: فرض کنیم $v\in V(G)$، به مجموعهٔ رأس‌هایی از گراف G که به رأس v متصل هستند، «همسایگی باز رأس v» می‌گوییم و با ${{N}_{G}}(v)$ نمایش می‌دهیم. اضافه کردن خود رأس v به ${{N}_{G}}(v)$ «همسایگی بستهٔ رأس v» را به‌دست می‌دهد که آن‌را با ${{N}_{G}}\left[ v \right]$ نمایش می‌دهیم. می‌توان این دو مجموعه را به‌صورت زیر نمایش داد:

${{N}_{G}}(v)=\left\{ u\in V(G)\,:\,\,uv\in E(G) \right\}$
${{N}_{G}}\left[ v \right]={{N}_{G}}(v)\bigcup \left\{ v \right\}$

به‌طور مثال در گراف شکل 12 داریم:

${{N}_{G}}(a)=\left\{ b \right\}$
${{N}_{G}}\left[ a \right]=\left\{ a,b \right\}$
${{N}_{G}}(c)=\left\{ b,d,g \right\}$
${{N}_{G}}\left[ c \right]=\left\{ b,c,d,g \right\} $
${{N}_{G}}(f)=\varnothing$
${{N}_{G}}\left[ f \right]=\left\{ f \right\}$

- دو یال مجاور: دو یال را مجاور گوییم هرگاه رأسی وجود داشته باشد که هر دوی آنها به آن متصل باشند. به‌طور مثال در شکل 12 ، یال‌های bc و cd مجاوراند.

- بزرگ‌ترین و کوچک‌ترین درجۀ یک گراف: بزرگ‌ترین عدد در بین درجات رئوس گراف G را با $\Delta (G)$ و کوچک‌ترین آنها را با $\delta (G)$ نمایش می‌دهیم و به‌ترتیب آنها را با ماکزیمم و مینیمم درجهٔ گراف می‌نامیم. به‌طور مثال در گراف شکل 13 داریم:

$\Delta (G)=3$
$\delta (G)=0$

- زیرگراف: یک زیرگراف از گراف G گرافی است که مجموعهٔ رئوس آن زیرمجموعه‌ای از مجموعهٔ رئوس گراف G، و مجموعهٔ یال‌های آن زیرمجموعه‌ای از مجموعهٔ یال‌های G باشد. به‌طور مثال گراف‌های ${{G}_{1}}$ و ${{G}_{2}}$ و ${{G}_{3}}$ که در شکل 15 آمده‌اند، زیرگراف‌هایی از گراف G در شکل 14 هستند.

- مکمل یک گراف: مکمل گرافی مانند G که آن‌را با ${{G}^{c}}$ یا $\overline{G}$ نمایش می‌دهیم گرافی است که مجموعهٔ رئوس آن همان مجموعهٔ رئوس گراف G است و بین دو رأس از ${{G}^{c}}$ یک یال است اگر و تنها اگر بین همان دو رأس در G یالی وجود نداشته باشد. در شکل 16 یک گراف و مکملش نمایش داده شده است.

مسئله 1: اگر G یک گراف با n رأس و v یک رأس آن باشد و ${{d}_{G}}(v)$ و ${{d}_{\overline{G}}}(v)$ به‌ترتیب درجهٔ رأس v در گراف‌های G و $\overline{G}$ باشند، مقدار ${{d}_{G}}(v)+{{d}_{\overline{G}}}(v)$ را به‌دست آورید.

مسئلهٔ 2: یک گراف با n رأسی حداکثر چند یال می‌تواند داشته باشد؟

مسئلهٔ 3: اگر G یک گراف n رأسی باشد، مقدار  $q(G)+q(\overline{G})$ را به‌دست آورید.

- گراف کامل: گرافی را که هر رأس آن با تمام رئوس دیگر، مجاور باشد گراف کامل می‌نامیم. گراف کامل n رأسی را با ${{K}_{n}}$ نمایش می‌دهیم. می‌توان گفت ${{K}_{n}}$ یک گراف n رأسی و $n-1$- منتظم است.

مسئله 1: یک گراف کامل p رأسی چند یال دارد؟
مسئله 2: اگر G یک گراف p رأسی باشد، چه رابطه‌ای بین تعداد یال‌های گراف‌های $G$، $\overline{G}$ و ${{K}_{p}}$ وجود دارد؟
مسئله 3: مکمل گراف کامل چه نوع گرافی است؟

- مسیر: اگر $u$ و $v$ دو رأس از گراف $G$ باشند، یک مسیر از $u$ به $v$ (یک $u-v$ مسیر) در $G$ دنباله‌ای از رئوس دوبه‌دو متمایز در $G$ است که از $u$ شروع و به $v$ ختم می‌شود به‌طوری‌که هر دو رأس متوالی این دنباله در $G$ مجاور هم باشند. طول یک مسیر برابر است با تعداد یال‌های موجود در آن مسیر (یکی کم‌تر از تعداد رئوس موجود در آن مسیر). قرارداد می‌کنیم که دنبالهٔ متشکل از تنها یک رأسِ $v$، یک مسیر است با طول صفر از رأس $v$ به خودش.

مثال
$uwv$ یک $u-v$ مسیر به طول 2 است.
$uzywv$ یک $u-v$ مسیر به طول 4 است.

- گرافی را که تنها از یک مسیر n رأسی تشکیل شده باشد با ${{P}_{n}}$ نمایش می‌دهیم. به‌طور مثال ${{P}_{5}}$ در شکل 18 نمایش داده شده است.

- دور: دنبالهٔ $(n\ge 3)\,{{v}_{1}}{{v}_{2}}{{v}_{3}}...{{v}_{n}}{{v}_{1}}$ از رئوس دوبه‌دو متمایز که در آن هر رأس با رأس بعدی مجاور است را یک دور به طول n می‌نامیم. به‌طور مثال در گراف شکل 17 $xwvuzyx\,,\,ywuzy\,,\,uvwu$ دورهایی به‌ترتیب با طول 3 و 4 و 6 هستند.

گرافی را که تنها از یک دورِ n رأسی تشکیل شده باشد را با ${{C}_{n}}$ نمایش می‌دهیم. به‌طور مثال ${{C}_{5}}$ در شکل 19 نمایش داده شده است.

مسئله: در گراف شکل 17، دوری به طول 5 بیابید.

- همبندی و ناهمبندی یک گراف: گراف G را همبند می‌نامیم هرگاه بین هر دو رأسِ آن حداقل یک مسیر وجود داشته باشد، در غیر این‌صورت آن‌را ناهمبند می‌نامیم. به‌طور مثال گراف H در شکل 20 همبند و گراف G ناهمبند است زیرا مثلاً بین رئوس v و w هیچ مسیری وجود ندارد.